import java.util.Arrays;

/**
 * @author WangTianyi
 * @create 2021-12-08 21:17
 */
public class Self_RadixSort {

    public static void main(String[] args) {
        int[] array1 = new int[]{421, 240, 115, 532, 305, 430, 124};
        int[] sortedArray1 = radixSort(array1,3);
        System.out.println(Arrays.toString(sortedArray1));
    }

    //低位优先的基数排序（Least Significant Digit First）
    public static int[] radixSort(int[] array, int digit){//digit表示数组中的数字最高有几位
        int[] result = new int[array.length];
        int[] count = new int[10];

        for(int i=0; i<digit; i++){//i代表轮数，先按照个位收集算是一轮，按照十位收集又算是一轮
            int division = (int)Math.pow(10,i);
            for(int j=0; j<array.length; j++){//j用于在每轮中遍历整个原数组（在上次收集和分配的基础上）
                int num = array[j]/division % 10;
                count[num]++;
            }

            for(int j=1; j<count.length; j++){//j用于遍历一趟count将其从计数数组变成累加数组
                count[j] = count[j] + count[j-1];
            }

            for(int j=array.length-1; j>=0; j--){//j用于在每轮中反序遍历整个原数组，在保持稳定性的前提下使其在本轮中有序
                int num = array[j]/division % 10;
                result[--count[num]] = array[j];
            }

            //重置array数组和count数组
            System.arraycopy(result, 0, array, 0, result.length);
            Arrays.fill(count, 0);
        }

        return result;
    }

    //一种空间复杂度高很多的基数排序写法
    public static int[] radixSortMini(int[] array, int digit){//digit代表最高位数
        int[][] count = new int[10][array.length+1];//count往往也命名为buckets（桶）
        for(int i=0; i<digit; i++){
            int division = (int)Math.pow(10, i);
            for(int j=0; j<array.length; j++){//j用于在每轮中遍历整个原数组（在上次收集和分配的基础上）
                int num = array[j]/division % 10;
                count[num][count[num][array.length]++] = array[j];
            }

            //接下来把桶中的数据还原会原数组
            int l = 0;
            for(int j=0; j<count.length; j++){
                for(int k=0; k<count[j][array.length]; k++){
                    array[l++] = count[j][k];
                }
            }

            //把count[][array.length]置为0
            for(int j=0; j<count.length; j++){
                count[j][array.length] = 0;
            }
        }
        return array;
    }
}
